package com.heima.algorithm.sort;

/**
 * <strong>冒泡排序</strong>
 * <p>思想：相邻元素比较，如果左边元素大于右边元素，则交换位置，每次冒泡都会找到一个最大的元素，然后放到未排序区间的末尾，未排序区间减一，然后继续冒泡，找到最大的元素放到未排序区间的末尾，直到未排序区间长度为1</p>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/28 12:37
 */
public class BubbleSort {
    //（1）基于比较的排序算法
    //（2）最好情况：O(N)，最坏情况：O(N^2)，平均：O(N^2)，空间：O(1)，稳定：是，思想：比较
    //（3）注意事项：最好的情况需要额外的判断是否需要交换

    /**
     * 冒泡排序非递归实现，递归版本在{@link com.heima.algorithm.recursion.BubbleSort}
     * @param arr 待排序的数组
     */
    public static void bubbleSort(int[] arr){
        // 边界：未排序的边界（包含）
        int bound = arr.length - 1;
        // 当未排序的边界（包含） > 0，继续循环，只剩一个未排序的元素 = 0，则退出循环
        while (true){
            // 用来记录一轮循环后新的边界
            int newBound = 0;
            // 因为冒泡排序是相邻元素比较，所以循环到边界内的倒数第二个元素，也就是bound - 1，否则可能会有数组索引越界问题
            for (int i = 0; i < bound; i++) {
                // 比较相邻元素，如果左边元素大于右边元素，则交换位置
                if (arr[i] > arr[i + 1]){
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    // 记录新的边界，因为交换到后面的那个元素可能还会再次被交换到更后面去，所以边界取i，也可以说newBound记录最后一次交换发生的位置，后面的都已经排序好了，减少不必要的比较次数
                    newBound = i;
                }
                // 没有发生交换则不记录新边界
            }
            // 更新边界
            bound = newBound;
            // 如果新边界为0，则说明已经全部排序完毕，退出循环
            if (bound == 0){
                return;
            }
        }
    }
}
